Глеб и медиана
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Глеб устал от побитового исключающего «или» и решил, что пора найти новую интересную функцию. Его выбор пал на медиану. Напомним, медианой массива называется число, которое окажется посередине, если массив упорядочить по возрастанию. В рамках этой задачи для массивов чётной длины положим медиану равной левому из двух центральных в отсортированном порядке элементов.

Для некоторого числа $$$m$$$ назовём $$$m$$$-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна $$$m$$$. Вам дан массив $$$a$$$ длины $$$n$$$ и $$$q$$$ запросов двух видов:

  1. присвоить элементу с индексом $$$i$$$ значение $$$x$$$;
  2. найти наибольшее число $$$k$$$ такое, что для подотрезка массива с индексами от $$$l$$$ до $$$r$$$ существует $$$m$$$-разбиение на $$$k$$$ отрезков.

Входные данные

В первой строке дается число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) - размер массива. В следующей строке вводятся $$$n$$$ чисел $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^9$$$) - элементы массива, на следующей строке вводится число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) - количество запросов. В следующих $$$q$$$ строках даются запросы, каждый в одном из следующих форматов:

Выходные данные

Для каждого запроса второго типа в отдельной строке выведите ответ на запрос. В случае если для отрезка не существует никакого $$$m$$$-разбиения, выведите $$$0$$$.

Система оценки

В задаче присутствуют 6 групп:

  1. $$$n \le 5, q \le 5$$$, такие решения будут набирать не менее 10% баллов
  2. $$$n \le 100, q \le 100$$$, такие решения будут набирать не менее 20% баллов
  3. $$$n \le 10000, q \le 10000$$$, такие решения будут набирать не менее 30% баллов
  4. $$$m$$$ - одно и тоже для всех запросов, такие решения будут набирать не менее 25% баллов
  5. нет запросов изменения, такие решения будут набирать не менее 35% баллов
  6. Ограничения, как и в задаче

Пример

Входные данные
5
1 2 3 4 5
4
2 2 1 3
1 1 5
2 5 1 5
2 4 4 5
Выходные данные
1
0
2